一、學習目標

• 理解「在答案範圍上做二分」的核心：把原問題改寫成「給定一個候選值 x，判定是否可行」的單調性判定。
• 熟悉兩大題型：
  • 最小化最大值（找第一個可行 x，lower bound on predicate）
  • 最大化最小值（找最後一個可行 x，upper bound on predicate）
• 能正確撰寫 check(x)（可行性判定函式）、選擇邊界與不變量（invariants），避免死循環與溢位。

二、觀念說明

什麼是「答案域二分法」？

傳統二分在索引/有序陣列上找值；答案域二分是在答案的數值範圍上做二分。
關鍵是把問題化為：存在一個單調性的判定 check(x)（例如：容量/速度/距離 ≥/≤ x 是否可行）。
若 x 可行，則所有更「寬鬆」的值也可行（或相反）；如此即可用二分找到臨界點。

兩種常見目標

1. 最小化最大值：例如「最小速度使得能在 H 小時內吃完」、「最小容量使得 D 天內運完」。
   目標：找第一個使 check(x)=true 的 x（lower_bound）。
2. 最大化最小值：例如「放球使相鄰距離≥d，最大化 d」。
   目標：找最後一個使 check(x)=true 的 x（upper_bound）。

三、CSES實戰演練

題目1 : Factory Machines

原題:
https://cses.fi/problemset/task/1620

題意:
n 台機器，第 i 台生產一個產品需時 t[i]。問至少生產 target 個產品所需的最小時間。

解題思路:
給定時間 X，可生產總量為 sum(X / t[i])。若 ≥ target → X 可行。
對 X 在 [1, max(t)*target] 二分，找第一個可行時間。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    long long target;
    cin >> n >> target;
    vector<long long> t(n);
    for (auto &x : t) cin >> x;

    // 時間答案的範圍：最小 0（或 1），最大 = 最快機器單獨生產 target 的時間
    long long lo = 0;
    long long hi = *min_element(t.begin(), t.end()) * target;

    auto ok = [&](long long X) -> bool {
        // 計算在時間 X 內能做多少件；提早截斷總和避免溢位
        long long made = 0;
        for (long long d : t) {
            long long add = X / d;
            if (made >= target - add) return true; // 等價於 made + add >= target，但不溢位
            made += add;
        }
        return made >= target;
    };

    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (ok(mid)) hi = mid;     // 可行，嘗試更短時間
        else lo = mid + 1;         // 不可行，時間太短
    }

    cout << lo << '\n';
    return 0;
}

時間複雜度:O(n log (max(t)*target))

題目2 : Array Division

原題:
https://cses.fi/problemset/task/1085

題意：
給長度 n 的正整數陣列與 k，將陣列切成至多 k 段，最小化「每段元素和的最大值」。輸出該最小可能值。

解題思路：

• 給上限 X，用貪心掃一遍：累積當前段和，若超過 X 就切新段；計數段數 cnt。
• 若 cnt ≤ k，表示容量 X 足以放下 → 可行。二分找第一個可行的 X。
• 下界 L = max(a[i])（至少能容納單個元素），上界 R = sum(a)。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k; 
    cin >> n >> k;
    vector<long long> a(n);
    long long L = 0, R = 0;
    for (auto &x : a) { cin >> x; L = max(L, x); R += x; }

    auto ok = [&](long long X)->bool {
        int cnt = 1;         // 至少一段
        long long sum = 0;
        for (auto v : a) {
            if (sum + v <= X) sum += v;
            else { ++cnt; sum = v; }
        }
        return cnt <= k;
    };

    long long lo = L, hi = R;
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (ok(mid)) hi = mid;
        else lo = mid + 1;
    }
    cout << lo << "\n";
    return 0;
}

時間複雜度：O(n log sum(a))

四、Leetcode實戰演練

題目1 : Koko Eating Bananas

原題:
https://leetcode.com/problems/koko-eating-bananas/
題意：
每堆香蕉 piles[i]，Koko 以速度 v（每小時吃 v 根，同一堆整小時計）吃，問在 H 小時內吃完的最小 v。

解題思路：

• check(v)：所需總時數 sum(ceil(piles[i]/v)) ≤ H。
• 對 v 在 [1, max(piles)] 二分找第一個可行速度。

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        long long lo = 1, hi = *max_element(piles.begin(), piles.end());
        auto ok = [&](long long v)->bool {
            long long need = 0;
            for (int x : piles) {
                need += (x + v - 1) / v; // ceil
                if (need > h) return false;
            }
            return need <= h;
        };
        while (lo < hi) {
            long long mid = lo + (hi - lo) / 2;
            if (ok(mid)) hi = mid;
            else lo = mid + 1;
        }
        return (int)lo;
    }
};

時間複雜度：O(n log max(piles))

題目2 : Magnetic Force Between Two Balls

原題:
https://leetcode.com/problems/magnetic-force-between-two-balls/

題意：
在座標陣列 position 放入 m 顆球，要求任兩球距離 ≥ d，求 d 的最大值。

解題思路（最大化最小值）：
先排序座標。check(d)：從最左開始能不能用「貪心放置」放滿 m 顆（每次盡量放在最左可放的位置）。
對距離 d 在 [0, max(position)-min(position)] 二分，找最後一個可行的 d。

class Solution {
public:
    int maxDistance(vector<int>& position, int m) {
        sort(position.begin(), position.end());
        int lo = 0, hi = position.back() - position.front();

        auto ok = [&](int d)->bool {
            int used = 1, last = position.front();
            for (int i = 1; i < (int)position.size(); ++i) {
                if (position[i] - last >= d) {
                    ++used; last = position[i];
                    if (used >= m) return true;
                }
            }
            return used >= m;
        };

        while (lo < hi) {
            int mid = lo + (hi - lo + 1) / 2; // 上中位，找最後一個可行
            if (ok(mid)) lo = mid;
            else hi = mid - 1;
        }
        return lo;
    }
};

時間複雜度：排序 O(n log n) + 二分每次 O(n) → O(n log n + n log R)